package problem198_House_Robber;

/**
 * r[i]=max(r[i-1],r[i-2]+nums[i])
 * @author I321035
 *
 */
public class Solution {
	public int rob(int[] nums) {
		if(nums.length==0)
			return 0;
		else if(nums.length==1)
			return nums[0];
		else if(nums.length==2)
			return Math.max(nums[0], nums[1]);
		int[] r=new int[nums.length];
		r[0]=nums[0];r[1]=Math.max(nums[0], nums[1]);
		for(int i=2;i<nums.length;i++){
			r[i]=Math.max(r[i-1], r[i-2]+nums[i]);
		}
		return r[r.length-1];
	}
	
	
	//降低空间复杂度 cur代表r[i-1], pre代表 r[i-2]
	public int rob2(int[] nums){
		if(nums.length==0)
			return 0;
		else if(nums.length==1)
			return nums[0];
		int cur=0,pre=0;
		for(int i=0;i<nums.length;i++){
			int tmp=cur;
			cur=Math.max(cur, pre+nums[i]);
			pre=tmp;
		}
		return cur;
	}
}
